package q560_subarraySum;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
    hash表的经典应用：
    相较于每次考虑一段数字加起来是否为k
    可以转化为前缀和问题 对于0 - i的一段数字前缀和为pre[i], 0 - j则为pre[j]
    那么如果pre[j] - pre[i] = k 也就代表 i - j这一段也是符合和为k的
    所以使用hash表可以实现o(n)的时间复杂
    需要注意的是需要加入if (sum == k) ans++;来判断一段数字之和直接为k的情况
     */
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0, ans = 0;

        for (int num : nums) {
            sum += num;
            if (sum == k) ans++;

            if (map.containsKey(sum - k)) {
                ans += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return ans;
    }
}
